package main.scala.KNNalgorithm

/**
 *  To achieve kd tree , we refer to https://blog.csdn.net/k_wzzc/article/details/103284888.
 */

class KdT{


  /**
   *
   * @param treeNode the root node of the kd tree
   * @param data query data or query node
   * @param k the number of nearest neighbors we want to get
   * @return an array with sie k that contains k node in the kd tree
   *         with format (Double, TreeNode)
   */
  def knn(treeNode: TreeNode, data: Seq[Double], k: Int): Array[(Double, TreeNode)] = {
    // Initialization of resArr with MaxValue filled.
    var resArr = new Array[(Double, TreeNode)](k)
      .map(_ => (Double.MaxValue, null))
      .asInstanceOf[Array[(Double, TreeNode)]]

    /**
     *
     * Call finder function to get k nearest neighbors.
     */
    def finder(treeNode: TreeNode): TreeNode = {

      if (treeNode != null) {

        /**
         * dim represent at which dimension data should be compared with each other
         * if the distance between query data and the treeNode is bigger than zero,
         * than the treeNode should lie in the left of the data space, so we should
         * look in the right node of the tree to search a nearer point than the current node treeNode.
         * The case should be similar when the distance is no bigger than zero.
         */
        val dimr = data(treeNode.dim) - treeNode.value(treeNode.dim)
        if (dimr > 0) finder(treeNode.right) else finder(treeNode.left)
        val distc: Double = euclidean(treeNode.value, data)


        /**
         * we begin to update the k neighbors
         * if current minimum distance is smaller than the last element
         * of resArr, we replace the last element of resArr with this candidate node.
         * Since the resArr is initialized with Double.maxValue, through the sortBy()
         * function resArr can be sorted in a ascending order, and Double.maxValue will be
         * replace by later smaller value.
         */
        if (distc < resArr.last._1  ) {
          resArr.update(k - 1, (distc, treeNode))
          resArr = resArr.sortBy(_._1)
        }

        if (math.abs(dimr) < resArr.last._1)
          if (dimr > 0) finder(treeNode.left) else finder(treeNode.right)

      }
      // if the treeNode is null, it represent we reached at the end side of the tree
      // but here it seems has no effect.
      resArr.last._2
    }

    finder(treeNode)
    resArr

  }


  /**
   *
   * @param p1 point p1
   * @param p2 point p2
   * @return the Euclidean distance  between
   *         p1 and p2 using formula:
   *         sqrt(sum(pow(x1-x2,2)))
   */
  def euclidean(p1: Seq[Double], p2: Seq[Double]): Double = {
    require(p1.size == p2.size)
    /**
     * from this code, the zip() function will return a Seq[(t,t)]
     */
    //    val tmp: Seq[(Double, Double)] = p1.zip(p2)
    val d = p1
      .zip(p2)
      .map(tp => math.pow(tp._1 - tp._2, 2))
      .sum
    math.sqrt(d)
  }


  /**
   *
   * @param treeNode a kd tree
   * @param data  query node or query point
   * @return  the nearest data node of query node.
   */
  def nearestSearch(treeNode: TreeNode, data: Seq[Double]): TreeNode = {
    // it is used to server as the nearest node of query node.
    var nearestNode: TreeNode = null
    // the minimum distance between nearestNode and query node or data.
    var minDist: Double = Double.MaxValue

    def finder(treeNode: TreeNode): TreeNode = {

      treeNode match {
        case null => nearestNode
        case _ =>
          /**
           * dim represent at which dimension data should be compared with each other
           * if the distance between query data and the treeNode is bigger than zero,
           * then the treeNode should lie in the left of the data space, so we should
           * look in the right node of the tree to search a nearer point than the current node treeNode.
           * The case should be similar when the distance is no bigger than zero.
           */
          val dimr = data(treeNode.dim) - treeNode.value(treeNode.dim)

          if (dimr > 0) finder(treeNode.right) else finder(treeNode.left)

          /**
           * when treeNode's children are null, we reached the bottom of the tree.
           * we begin to update the minimum distance between the query
           * data and current node.
           */

          val distc = euclidean(treeNode.value, data)
          if (distc <= minDist) {
            minDist = distc
            nearestNode = treeNode
          }

          /**
           * when the updated minDist is smaller than selected smallest distance,
           * it represents that at current dimension and at current side of tree,
           * we find a node which is better than its parent node, and we have to
           * look into its children to get a better solution again, but we have two
           * choices： its left node and right node, and we can verify that
           * we should look at the direction that make the distance between query node and
           * candidate node smaller.
           */
          if (math.abs(dimr) < minDist)
            if (dimr > 0) finder(treeNode.left) else finder(treeNode.right)

          nearestNode
      }
    }

    finder(treeNode)

  }

  /**
   *
   * @param value the content of the data node
   * @param dim   at which dimension the data is to be sorted.
   * @param shape the dimension of the data
   * @return  the root node of constructed binary tree.
   */
  def creatKdTree(value: Seq[Seq[Double]], dim: Int, shape: Int): TreeNode = {

    /**
     * sort the value variable by its dim-th dimension,
     * at the beginning, dim is 0.
     */
    //    val sorted = value.sortBy(_ (dim))
    val sorted: Seq[Seq[Double]] = value.sortBy(x => x (dim))
    // Compute the middle index of sorted, and its corresponding element as the root node.
    /**
     * Plan:
     * data space split
     *
     * given a set of x called S, the median of S
     * lies in the Pth position which satisfies :
     * let len(S) = lens
     *
     *
     * if lens is odd：
     *
     *      midIndex =  (lens-1)/2
     *
     * else:
     *
     *      midIndex = lens/2 (order is left to right, bottom to top)
     */
    //    val midIndex: Int = value.length / 2
    val lens = value.length
    val midIndex: Int =   if (lens % 2 == 0) lens/2 else  (lens-1)/2
    sorted match {
      /**
       * Here is an end condition
       * if sorted has zero element ,return null
       * in this condition lef node and right node will be null,
       * and when call  TreeNode , we get a tree that has a non-null root node and
       * has null left node and right node.
       * After that the trees will be merged into a big tree from bottom to top.
       */
      case Nil => null
      //otherwise, constructing the kd tree.
      case _ =>
        // we take the sorted[0,midIndex-1] and sorted[midIndex+1,lens-1] as left part
        // and right part, then call the createKdTree itself.
        val left = sorted.slice(0, midIndex)
        val right = sorted.slice(midIndex + 1, value.length)


        /**
         *
         * in left part, we sort it at (dim + 1) % shape -th dimension and
         * shape represents the dimension of the node content.
         */
        val leftNode: TreeNode = creatKdTree(left, (dim + 1) % shape, shape)
        /**
         *
         * in right part, we do the same as in left part.
         */
        val rightNode = creatKdTree(right, (dim + 1) % shape, shape)

        /**
         *
         * Here, we have got the right node,left node, and root node, so
         * now we can construct a tree using these three nodes.
         */
        TreeNode(sorted(midIndex), dim, leftNode, rightNode)

    }
  }

  /**
   *
   * @param Root root node of the kd tree
   * @return checked root node,if this node is not a root node
   *         throws IllegalArgumentException
   */
  def TreeRoot(Root:TreeNode):TreeNode ={

    if (Root.parent==null && (Root.left!=null || Root.right!=null)){
      Root
    }
    else  null

  }

  /**
   *
   * @param Node the root of kd tree which is to be traversed
   */
  def GenPreOrder(Node:TreeNode): Unit ={
    this.preOrder(TreeRoot(Node))
  }

  def someProcess(): Unit = {
    println("---hold on,some preprocess --")
  }

  // preorder of kd tree
  private  def preOrder(CurP:TreeNode): Unit ={
    //print state of current node
    printf("-->current node-->"+ CurP.value.mkString(","))
    //   do some preprocess
    someProcess()
    if (CurP.left != null){
      preOrder(CurP.left)
    }
    if (CurP.right != null){
      preOrder(CurP.right)
    }
  }




}